//
// Created by Administrator on 2021/5/23.
//

/*在一个仓库里，有一排条形码，其中第 i 个条形码为barcodes[i]。

请你重新排列这些条形码，使其中两个相邻的条形码 不能 相等。 你可以返回任何满足该要求的答案，此题保证存在答案。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/distant-barcodes
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。*/


#include <vector>
#include <iostream>
#include <unordered_map>
#include <queue>
#include <algorithm>

using namespace std;

// 看起来和767、重构字符串类似
// 优先放数量最多的
class Solution {
public:
    vector<int> rearrangeBarcodes(vector<int> &barcodes) {
        unordered_map<int, int> fre;
        for (auto &x:barcodes) ++fre[x];
        auto cmp = [](pair<int, int> &a, pair<int, int> &b) {
            return a.second < b.second;
        };
        priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(cmp)> q(cmp); // 大堆顶
        for (auto &x:fre) q.emplace(x.first, x.second);
        vector<int> ans;
        while (!q.empty()) {
            // 每次塞一个条形码
            // 可以直接塞
            if (ans.empty() or ans.back() != q.top().first) {
                auto temp = q.top();
                q.pop();
                ans.push_back(temp.first);
                if (--temp.second > 0) q.push(temp);
            } else { // 不能直接塞 需要塞下一个数量最多的数字
                auto temp1 = q.top();
                q.pop();
                auto temp2 = q.top();
                q.pop();
                ans.push_back(temp2.first);
                if (--temp2.second > 0) q.push(temp2);
                q.push(temp1);
            }
        }
        return ans;
        // AC 20% 能不能一次塞两个码？
    }

    vector<int> rearrangeBarcodes2(vector<int> &barcodes) {
        unordered_map<int, int> num_freq;
        for (int x: barcodes) num_freq[x]++;
        priority_queue<pair<int, int>, vector<pair<int, int>>, less<>> maxHeap;
        for (auto[x, fx] : num_freq)
            maxHeap.push(pair<int, int>{fx, x});
        //------------------ 每次选取freq最大的2个数字，添加进res
        vector<int> res;
        while (maxHeap.size() >= 2) {
            auto[fx, x] = maxHeap.top();
            maxHeap.pop();
            auto[fy, y] = maxHeap.top();
            maxHeap.pop();
            res.push_back(x);
            res.push_back(y);
            if (fx - 1 > 0)
                maxHeap.push(pair<int, int>{fx - 1, x});
            if (fy - 1 > 0)
                maxHeap.push(pair<int, int>{fy - 1, y});
        }
        if (!maxHeap.empty()) {
            res.push_back(maxHeap.top().second);
        }
        return res;
    }

    vector<int> rearrangeBarcodes3(vector<int> &barcodes) {
        int n = (int) barcodes.size();
        unordered_map<int, int> num_freq;
        for (int x: barcodes)
            num_freq[x]++;
        //------------- 按照freq降序排列
        vector<pair<int, int>> a;
        a.reserve(num_freq.size());
        for (auto[x, fx] : num_freq)
            a.emplace_back(x, fx);
        sort(a.begin(), a.end(), [&](const pair<int, int> &a, const pair<int, int> &b) {
            return a.second > b.second;
        });
        //-------------间隔插入 相当于将结果分为 奇 偶 两列 按顺序先填满奇数列，再填满偶数列
        vector<int> res(n);
        int i = 0;
        for (auto[x, fx] : a) {
            for (int _ = 0; _ < fx; _++) {
                if (i >= n)
                    i = 1;
                res[i] = x;
                i += 2;
            }
        }
        return res;

    }
};


int main() {
    vector<int> v{1, 1, 1, 2, 2, 2};
    vector<int> v2{1, 1, 1, 1, 2, 2, 3, 3};
    Solution sol;
    auto ans = sol.rearrangeBarcodes3(v2);
    for (auto &x:ans) cout << x << endl;
    return 0;
}


